package KMP;

public class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();


        for(int i=0;i+n<=m;i++){
            String sub = haystack.substring(i,i+n);
            if(sub.equals(needle)){
                return i;
            }
        }

        return -1;
    }

    public int strstr(String haystack, String needle) {
        if(needle.length()==0) return 0;
        int m = haystack.length(), i = 0;
        int n = needle.length(),   j = 0;

        int[] next = nextBuilder(needle);
        while(i<m && j<n) {
            if(j<0 || haystack.charAt(i) == needle.charAt(j)) {
                i++;j++;
            }else{j = next[j];}
        }
        if(j == n) { return i - j;}
        else return -1;
    }
    private int[] nextBuilder(String needle) {
        int m = needle.length();
        int[] next = new int[m];
        next[0] = -1;
        int t = -1, j = 0;
        while(j < m-1) {
            if(t < 0 || needle.charAt(t) == needle.charAt(j)) {
                t++;
                j++;
                next[j] = t;
            } else { t = next[t];}
        }
        return next;
    }
}
